package leetcode;

import java.util.*;

public class Code818 {
    public static void main(String[] args) {
        System.out.println(new Code818().racecar2(5));
    }

    public int racecar(int target) {
        //加2防止target过小，省去写多个if-return
        int[] dp = new int[target + 2];
        Arrays.fill(dp, Integer.MAX_VALUE);

        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 4;

        for (int i = 3; i <= target; i++) {
            //注意这里的技巧，32 - numberOfLeadingZeros(i)返回i的最高位从右往左对应的下标
            //例如11返回2
            int k = 32 - Integer.numberOfLeadingZeros(i);
            //最好的情况，直接等于k
            if ((1 << k) - 1 == i) {
                dp[i] = k;
                continue;
            }
            int before =(1<<(k-1))-1;
            int end = (1<<(k))-1;

            dp[i] = Math.min(dp[i], dp[i - before] + dp[before] + 2);
            if ((1 << k) - 1 - i < i) {
                dp[i] = Math.min(dp[i], dp[(1 << k) - 1 - i] + k + 1);
            }
        }

        return dp[target];
    }

    public int racecar2(int target) {
        //加2防止target过小，省去写多个if-return
        int[] dp = new int[target + 2];
        Arrays.fill(dp, Integer.MAX_VALUE);

        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 4;

        for (int i = 3; i <= target; i++) {
            //注意这里的技巧，32 - numberOfLeadingZeros(i)返回i的最高位从右往左对应的下标
            //例如11返回2
            int k = 32 - Integer.numberOfLeadingZeros(i);
            //最好的情况，直接等于k
            if ((1 << k) - 1 == i) {
                dp[i] = k;
                continue;
            }

            /**
             * 没劲 直走 掉头 再直走
             */
            for (int j = 0; j < k - 1; j++) {
                dp[i] = Math.min(dp[i], dp[i - ((1 << (k - 1))-1) + (1 << j)-1] + k - 1 + j + 2);
            }
            /**
             * 直走超过 回头
             */
            if ((1 << k) - 1 - i < i) {
                dp[i] = Math.min(dp[i], dp[(1 << k) - 1 - i] + k + 1);
            }
        }

        return dp[target];
    }
}
